package com.example.demo;

public class UnionFind {
    private int[] parents;
    private double[] values;
    public UnionFind(int n){
        parents=new int[n];
        values=new double[n];
        for(int i=0;i<n;i++){
            parents[i]=i;
            values[i]=1.0d;
        }
    }
    public void union(int x,int y,double value){
        int parentX=find(x);
        int parentY=find(y);
        if(parentX==parentY){
            return;
        }
        parents[parentX]=parentY;
        values[parentX]=value*values[y]/values[x];
    }
    private int find(int x){
        if(x!=parents[x]){
            int curr=parents[x];
            parents[x]=find(parents[x]);
            values[x]*=values[curr];
        }
        return parents[x];
    }
    public  double isConnected(int x,int y){
        int parentX=find(x);
        int parentY=find(y);
        if(parentX!=parentY){
            return -1d;
        }
        return values[x]/values[y];
    }
}
